home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / docs / hyper / IndexAG.lha / IndexAG / sorting_chained_strcuture < prev    next >
Encoding:
Internet Message Format  |  1998-12-01  |  7.1 KB
  1. From abe49@hotmail.com Tue, 1 Dec 1998 14:06:19 -0600
  2. X-SystemInfo: Internet: EMail
  3. X-Message-No: 918 (database)
  4. From: abe49 <abe49@hotmail.com>
  5. To: boisvert <boisvert@hotpop.com>
  6. Subject: Re: sorting chained strcutures - how?
  7. Date: Tue, 1 Dec 98 15:06:00
  8. Message-ID: <199812012006.OAA15640@x14.dejanews.com>
  9. Reply-To: abe49@hotmail.com 
  10. Return-Path: <www@dejanews.com>
  11. Received: from m1.dejanews.com (m1.dejanews.com [208.10.192.32])by mail.hotpop.com (8.9.1/8.9.1) with ESMTP id QAA09181for <boisvert@hotpop.com>; Tue, 1 Dec 1998 16:18:04 GMT
  12. X-Advertisement: --------------------------------------------Sent By HotPOP.com FREE Email       Get your FREE POP email at www.HotPOP.com --------------------------------------------
  13. Received: from x14.dejanews.com (ix14.dejanews.com [10.2.1.205])by m1.dejanews.com (8.8.5/8.8.5) with ESMTP id OAA18798for <boisvert@hotpop.com>; Tue, 1 Dec 1998 14:06:20 -0600
  14. Received: (from www@dejanews.com)by x14.dejanews.com (8.7.6/8.6.12) id OAA15640; Tue, 1 Dec 1998 14:06:19 -0600
  15. X-maf:  
  16. Status:   
  17.  
  18. ------------------------------------------------------------------------------
  19.  
  20. This message was forwarded to you from Deja News by abe49@hotmail.com.
  21. Deja News, the discussion network, offers free web-based access to more than 
  22. 50,000 high-quality discussion forums. Come and visit us on the web at 
  23. http://www.dejanews.com/=zzz_maf/
  24.  
  25. ------------------------------------------------------------------------------
  26.  
  27. Sponsored by: Audio Book Club
  28. Join and get 4 bestselling audiobooks 1c
  29. http://www.audiobookclub.com/micro/home.asp?AID=S036L004B009
  30.  
  31. ------------------------------------------------------------------------------
  32.  
  33. (beginning of original message)
  34.  
  35. Subject: Re: sorting chained strcutures - how?
  36. From: heinz@hwg.muc.de (Heinz Wrobel)
  37. Date: 1996/09/15
  38. Newsgroups: comp.sys.amiga.programmer
  39.  
  40. Reinhard Katzmann (Suamor@student.uni-tuebingen.de) wrote:
  41. >   /* Sort the Array */
  42.  
  43. Hmm. If you use insertion sort, why are you using the backup array
  44. with those list pointers at all? You are working your way through
  45. the list sequentially, sorting in the "current" element at the
  46. "right" position. This means IMHO that you might as well walk the
  47. list directly to find the insertion point and use Exec List
  48. functions to remove and re-insert the node at the right position.
  49. You just have to stash the ln_Succ pointer before removing the
  50. current node.
  51.  
  52. How about this as general insertion sort based approach?
  53.  
  54. /*------------------------------------------------------------------------*/
  55. /*                                                                        *
  56.  *  $Id: sortminlist.c 1.1 1996/09/15 07:42:23 heinz Exp $
  57.  *                                                                        */
  58. /*------------------------------------------------------------------------*/
  59.  
  60. /*------------------------------------------------------------------------*/
  61. /*
  62.  * A simple Insertion Sort based MinList sort function with a test case
  63.  * (C)1996 by Heinz Wrobel, <heinz@hwg.muc.de>
  64.  *
  65.  * Based on SAS/C 6.56. Use a command line like this to check this out:
  66.  *  SC $*.c LINK DEF=TEST
  67.  */
  68. /*------------------------------------------------------------------------*/
  69. #include <exec/types.h>
  70. #include <exec/lists.h>
  71.  
  72. #define __USE_SYSBASE   /* SAS/C magic */
  73. #include <proto/exec.h> /* SAS/C magic */
  74.  
  75. /*------------------------------------------------------------------------*/
  76. void SortMinList(struct MinList *mlh,
  77.                  LONG cmpcallback(APTR mn1, APTR mn2))
  78. {
  79.     struct MinNode *mn1, *mn2, *mnnext;
  80.  
  81.     /* We are doing a simple insertion like sort here, working our way
  82.      * sequentially through the list. The runtime should be acceptable
  83.      * for smaller lists. MinLists are used because this is the lowest
  84.      * common denominator for all lists. I always felt that it is better
  85.      * to cast something down than to cast it upwards.
  86.      */
  87.  
  88.     /* This makes sense only if we have more than one node in the list! */
  89.     mn1 = mlh->mlh_Head;
  90.     if(mn1->mln_Succ)
  91.     {
  92.         /* While there is still a current node to sort in, sort it in.
  93.          * We stash the next pointer right away to avoid losing it on
  94.          * node removal. Note how we also skip the very first node!
  95.          */
  96.         for(mn1 = mn1->mln_Succ;
  97.             mnnext = mn1->mln_Succ;
  98.             mn1 = mnnext)
  99.         {
  100.             /* Work our way backwards to find
  101.              * the correct insertion point
  102.              */
  103.             for(mn2 = mn1->mln_Pred;
  104.                 mn2->mln_Pred;
  105.                 mn2 = mn2->mln_Pred)
  106.             {
  107.                 /* Our callback must return the same values
  108.                  * strcmp would return:
  109.                  *      <0  : mn1 <  mn2
  110.                  *      =0  : mn1 == mn2
  111.                  *      >0  : mn1 >  mn2
  112.                  * We stop when we find a node that is smaller than the
  113.                  * current one and insert our node after it
  114.                  */
  115.                 if(cmpcallback(mn1, mn2) > 0)
  116.                 {
  117.                     break;
  118.                 } /* if */
  119.             } /* for */
  120.  
  121.             /* Only do something, if we are not at
  122.              * the correct position yet
  123.              */
  124.             if(mn2->mln_Succ != mn1)
  125.             {
  126.                 /* Remember how we stashed the next pointer to continue! */
  127.                 Remove((struct Node *)mn1);
  128.                 Insert((struct List *)mlh,
  129.                        (struct Node *)mn1, (struct Node *)mn2);
  130.             } /* if */
  131.         } /* while */
  132.     } /* if */
  133.  
  134. } /* SortMinList */
  135.  
  136. /*------------------------------------------------------------------------*/
  137. #ifdef TEST
  138. #define USE_BUILTIN_MATH    /* SAS/C magic. Not really needed */
  139. #include <stdio.h>
  140. #include <stdlib.h>
  141. #include <strings.h>
  142.  
  143. LONG cmpcallback(struct Node *n1, struct Node *n2)
  144. {
  145.     return(strcmp(n1->ln_Name, n2->ln_Name));
  146.  
  147. } /* cmpcallback */
  148.  
  149. int main(int argc, char **argv)
  150. {
  151.     struct List lh;
  152.     struct Node *n, *nextn;
  153.     char buf[512];
  154.  
  155.     /* Read lines from stdin and print them sorted to stdout */
  156.     NewList(&lh);
  157.     while(fgets(buf, sizeof(buf) - 1 /* Paranoia */, stdin))
  158.     {
  159.         n = (struct Node *)malloc(sizeof(struct Node) + strlen(buf) + 1);
  160.         if(n)
  161.         {
  162.             n->ln_Name = (char *)(n + 1);
  163.             strcpy(n->ln_Name, buf);
  164.             AddTail(&lh, n);
  165.         } /* if */
  166.     } /* while */
  167.  
  168.     /* Now sort the list */
  169.     SortMinList((struct MinList *)&lh, cmpcallback);
  170.  
  171.     /* And finally print it */
  172.     for(n = lh.lh_Head;
  173.         nextn = n->ln_Succ;
  174.         n = nextn)
  175.     {
  176.         fputs(n->ln_Name, stdout);
  177.     } /* for */
  178.  
  179.     return(0);
  180.  
  181. } /* main */
  182. #endif /* TEST */
  183.  
  184. /*------------------------------------------------------------------------*/
  185.  
  186. /* EOT */
  187.  
  188. -- 
  189. Heinz Wrobel        Private Mail:   heinz@hwg.muc.de
  190. My private FAX: +49 89 850 51 25, I prefer email
  191.  
  192.  
  193. (end of original message)
  194. ------------------------------------------------------------------------------
  195.  
  196. You can view this message and the related discussion by following this link:
  197. http://www.dejanews.com/=zzz_maf/dnquery.xp?search=thread&svcclass=dnserver&recnum=%3cheinz.1don@hwg.muc.de%3e%231/2
  198. We hope to see you soon at Deja News, the discussion network.
  199. http://www.dejanews.com/=zzz_maf/
  200.  
  201.